/* =============================================================
 * Your Grandmother's guide to Algorithms
 * =============================================================
 *
 * Copyright (c) 2007, Saverio Miroddi
 *
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without 
 * modification, are permitted provided that the following conditions are met:
 * 
 *     * Redistributions of source code must retain the above copyright notice,
 *       this list of conditions and the following disclaimer.
 *     * Redistributions in binary form must reproduce the above copyright 
 *       notice, this list of conditions and the following disclaimer in the 
 *       documentation and/or other materials provided with the distribution.
 *     * Neither the name of the SaverioMiroddiSoftware nor the names of its 
 *       contributors may be used to endorse or promote products derived from 
 *       this software without specific prior written permission.
 * 
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER 
 * OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
 * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
 * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 *  
 * ---------------------------
 * BTree.java
 * ---------------------------
 *
 */
package btree;

import static btree.AbstractNode.NULL_NODE;
import java.util.Iterator;
import static btree.BTree.DeletionReturn.ChildEvent.ROOT_COLLAPSE;

public class BTree 
{
	public static boolean FULL_DEBUG = false;
	
	private AbstractNode _root;
	private final int _order;

	public static final long SEARCH_VAL_NOT_FOUND = -1L;
	
	public BTree(int order) 
	{
		_root = new LeafNode(order);
		_order = order;
	}
	
	public void add(
			Comparable<?> value, long recordPtr) 
	{
		if (value == null)  throw new UnsupportedOperationException("null values not supported");

		RecElement newRecElem = new RecElement(value, recordPtr);
		AdditionReturn newVal = _root.add(newRecElem);
		
		// we have a new root!
		if (newVal != null) {
			AbstractNode newRoot = new InternalNode(newVal.element, _order, newVal.rightNode);
			_root = newRoot;
		}
	}
	
	public long search(
			Comparable<?> value)
	{
		if (value == null) throw new UnsupportedOperationException("null values not supported");

		return _root.search(value);
	}
	
	public boolean remove(
			Comparable<?> value)
	{
		if (value == null) throw new UnsupportedOperationException("null values not supported");
		
		DeletionReturn removed = _root.remove(value, NULL_NODE, NULL_NODE);
		
		if (removed == null) {
			return false;
		}
		else if (removed.childEvent == ROOT_COLLAPSE) {
			_root = _root._rightPtr;
		}		
		return true;
	}
	
	public Iterator<Long> orderedTraversal()
	{
		return _root.orderedTraversal();
	}
	
	public AbstractNode getRootNode()
	{
		return _root;
	}
	
	/////////////////////////////////////////////////////////////////////////////////
	// CLASSES REPRESENTING THE RESULT AND THE DESCRIPTION OF WHAT THE CHILDREN DID
	// Member variables could be used but this is cleaner and more OO.
	/////////////////////////////////////////////////////////////////////////////////

	/**
	 * Represent the return value of an addition in the case split happened.
	 */
	protected static class AdditionReturn
	{
		public final NodeElement element;
		public final AbstractNode rightNode;

		public AdditionReturn(
				NodeElement splitHappens, AbstractNode rightNode) 
		{
			this.element = splitHappens;
			this.rightNode = rightNode;
		}
	}
	
	/**
	 * Represent the data needed for operation following a deletion:<br>
	 * the new rightmost value of the new node which contained the deleted element; and
	 * a flag indicating the operation which happened.
	 */
	@SuppressWarnings("unchecked")
	protected static class DeletionReturn
	{
		public enum ChildEvent {
			// misbehaving children
			STOLE_LEFT, 		// bubbles both the child rightmost value and
								// the child's left sibling's rightmost.
			STOLE_RIGHT, 
			/** WATCH OUT! Since for leaf nodes we must retain the left node
			 * (because of the left-left pointer to it), it's rule for every
			 * kind of node that the retaining node is the left one. This is
			 * inconsistent with the logic of MERGE_RIGHT, and the calling 
			 * code must take into account this fact. */
			MERGE_LEFT, 
			MERGE_RIGHT,
			CHANGED_RIGHTMOST,	// same effect as STOLE_RIGHTs 
			NO_VALUECHG,
			ROOT_COLLAPSE		// when the root node is internal and has zero 
								// elems
		}
		
		public final Comparable value;
		/** Used only by stole left */
		public final Comparable leftNodeValue;
		public final ChildEvent childEvent;

		public DeletionReturn(
				ChildEvent childEvent, Comparable value) 
		{
			this(childEvent, value, null);
		}
		
		public DeletionReturn(
				ChildEvent childEvent, Comparable value, Comparable leftNodeValue) 
		{
			assert(! (value instanceof AbstractElement || 
					  leftNodeValue instanceof AbstractElement));
			
			
			this.value = value;
			this.leftNodeValue = leftNodeValue;
			this.childEvent = childEvent;
		}
	}
}
